# 
# Automaton.rb - Implementation of non deterministic finite state machine,
#                also known as 'automaton'
#

require 'ParseException'

class Automaton

  attr_reader :ic, :state1, :state2

  EMPTY_STATE = "#"
  
  PLUS = 43
  OPEN_PARENTHESIS = 40
  CLOSED_PARENTHESIS = 41
  STAR = 42
  
  # Initialization of the instance.
  def initialize(string)
    @ic = []         # Array of tokens 
    @state1 = []     # Array of states for the main branch of the automaton
    @state2 = []     # Array of states for secondary branches of the automaton
    @q = -1          # Current state
    @s = string      # String containing the regular expression
    @i = 0           # Index of current charachter of the reg. expression
    @validtokens = "abcdefghijklmnopqrstuvxywzABCDEFGHIJKLMNOPQRSTUVXYWZ0123456789 "
  end
  
  # Begins parsing of the regular expression.
  #
  # Returns the first state of the automaton.
  def espressione()
    first_state = termine(false)
    
    if (@s[@i] == PLUS)
      m1_first_state = first_state
      m1_last_state = @q
      @q = @q + 1
      @i = @i + 1
      first_state = @q
      m2_first_state = espressione()
      
      transition(first_state, EMPTY_STATE, m2_first_state, m1_first_state)
      transition(m1_last_state, EMPTY_STATE, @q, @q)
    end
    
    return first_state
  end

  # Analyzes a term of the regular expression.
  def termine(connected)
    first_state = fattore(connected)
    if (@s[@i] != nil) && ((@s[@i] == OPEN_PARENTHESIS) or @validtokens.include?(@s[@i]))
      m2_first_state = termine(true)
    end
    return first_state   
  end
  
  # Analyzes a factor of the regular expression.
  def fattore(connected)
    previous_last_state = @q
    
    if (@validtokens.include?(@s[@i]))
      @q = @q + 1
      m2_first_state = @q
      
      transition(m2_first_state, EMPTY_STATE, @q + 1, @q + 1)
      
      @q = @q + 1
      
      transition(@q, @s[@i], @q + 1 , @q + 1)
      
      @i = @i + 1
      @q = @q + 1
    else
      if (@s[@i] == OPEN_PARENTHESIS)
        @i = @i + 1
        m2_first_state = espressione()
        if (@s[@i] == CLOSED_PARENTHESIS)
          @i = @i + 1
        else
          raise ParseException, "Syntax error while parsing regular expression."
        end
      else
        raise ParseException, "Syntax error while parsing regular expression."
      end
    end

    if (@s[@i] == STAR)
      transition(@q, EMPTY_STATE, @q + 1, @q + 1)
      
      @q = @q + 1
      tmp_state = @q
      @q = @q + 1
      final_state = @q
      
      transition(final_state, EMPTY_STATE, tmp_state, tmp_state)
      transition(tmp_state, EMPTY_STATE, @q + 1, m2_first_state)
      
      @q = @q + 1
      @i = @i + 1
    else
      final_state = m2_first_state
    end
    
    if (connected)
      transition(previous_last_state, EMPTY_STATE, final_state, final_state)
    end
    
    return final_state
  end
  
  # Adds a transition the arrays of the automaton.
  def transition(current_state, next_token, next_state1, next_state2)
    @ic[current_state] = next_token
    @state1[current_state] = next_state1
    @state2[current_state] = next_state2    
  end
  
end
